Internet communication is distributed among many nodes operating in conjunction with each other aiming at a particular task, and the degree of interdependence among those nodes is increasing. Furthermore, peer-to-peer communication, grid computing, cluster computing and ALM (application layer multicasting) or the like are new technologies relying on cooperation and communication among many nodes. Applications using these technologies are required to construct a metric tree describing delays among nodes of a network in order to accurately execute interdependent tasks. This is because delays among arbitrary nodes can be immediately estimated by constructing the metric tree.
However, when the number of nodes to be measured is N, if delays are measured in full-mesh according to round robin algorithm, the number of measurements performed becomes N×N−1. Therefore, when there are many nodes to be measured, a long processing time, high computation capacity and large storage capacity are required to construct a metric tree. When the burden is large in this way, depending, for example, on application, a situation may occur in which when the construction of the metric tree is completed, the timing at which the metric tree is required may have already passed.
Therefore, for example, Non-Patent Literature 1 describes a technology that every time a new node is added to a network, a delay between the joining node and a node of a known metric tree is measured and the measurement result is added to the metric tree. According to this technology, it is possible to construct a metric tree without performing delay measurement in full mesh.
However, the technology described in Non-Patent Literature 1 can estimate delays with respect to other nodes which are not measured with only low accuracy.
Therefore, for example, Patent Literature 1 describes a technology of selecting two nodes estimated to be nearest to (distance from) a joining node as a measurement target. According to this technology, it is possible to estimate delays with respect to other nodes which are not measured, with high accuracy.